// https://leetcode.cn/problems/3sum/

// 算法思路总结：
// 1. 先对数组进行排序
// 2. 固定最大数，转化为两数之和问题
// 3. 使用双指针在剩余范围内寻找目标值
// 4. 跳过重复元素避免重复解
// 5. 时间复杂度：O(n²)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());

        int n = nums.size();
        vector<vector<int>> ret;

        for (int k = n - 1 ; k >= 2 ; )
        {
            int target = -nums[k];
            for (int i = 0, j = k - 1 ; i < j ; )
            {
                int sum = nums[i] + nums[j];
                if (sum == target)
                {
                    ret.push_back({nums[i], nums[j], nums[k]});
                    i++; j--;
                    while (i < j && nums[j] == nums[j + 1])
                        j--;   
                    while (i < j && nums[i] == nums[i - 1])
                        i++;                 
                }
                else if (sum > target)
                {
                    j--;
                    while (i < j && nums[j] == nums[j + 1])
                        j--;
                }
                else
                {
                    i++;
                    while (i < j && nums[i] == nums[i - 1])
                        i++;
                }
            }
            k--;
            while (k >= 2 && nums[k] == nums[k + 1])
                k--;
        }
        return ret;
    }
};

int main()
{
    vector<int> v1 = {-1,0,1,2,-1,-4}, v2 = {0,0,0};
    Solution sol;

    auto vv1 = sol.threeSum(v1), vv2 = sol.threeSum(v2);

    for (const auto& v : vv1)
    {
        for (const auto& num : v)
            cout << num << " ";
        cout << endl;
    }
    cout << endl;

    for (const auto& v : vv2)
    {
        for (const auto& num : v)
            cout << num << " ";
        cout << endl;
    }


    return 0;
}